package com.javaDemo.node;

class Solution1 {
    public static boolean search(TreeNode r, TreeNode t){
        if(r==null){
            return false;
        }
        if(r==t){
            return true;
        }
        if(search(r.left,t)){
            return true;
        }
        if(search(r.right,t)){
            return true;
        }
        return false;
        
    }
   
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p==root||q==root){
            return root;
        }                                        //这两个节点至少一个是根节点
        boolean ph=search(root.left,p);
        boolean pf=search(root.right,q);
        boolean phi=search(root.right,p);
        boolean pfi=search(root.left,q);
        
        if(ph&&pf||phi&&pfi){  //  一个在左子树，一个在右子树
            return root;
        }
        if(ph&&pfi){
            return lowestCommonAncestor(root.left,p,q);           //两个都在左子树
            
        }
        return lowestCommonAncestor(root.right,p,q);             //两个都在右子树
        
        
    }
    public static void main(String[] args) {
        Integer[] root = {3,5,1,6,2,0,8,7,4};
        TreeNode p=new TreeNode(6);
        TreeNode q=new TreeNode(0);
        System.out.println(lowestCommonAncestor(TreeNode.makeTree(root),p,q));
    }
}
